Search results for "Lehmer code"

showing 3 items of 3 documents

Lehmer code transforms and Mahonian statistics on permutations

2012

Abstract In 2000 Babson and Steingrimsson introduced the notion of vincular patterns in permutations. They show that essentially all well-known Mahonian permutation statistics can be written as combinations of such patterns. Also, they proved and conjectured that other combinations of vincular patterns are still Mahonian. These conjectures were proved later: by Foata and Zeilberger in 2001, and by Foata and Randrianarivony in 2006. In this paper we give an alternative proof of some of these results. Our approach is based on permutation codes which, like the Lehmer code, map bijectively permutations onto subexcedant sequences. More precisely, we give several code transforms (i.e., bijections…

Discrete mathematicsCode (set theory)Mathematics::CombinatoricsValue (computer science)020206 networking & telecommunications0102 computer and information sciences02 engineering and technologyMathematical proof01 natural sciencesPermutation codeTheoretical Computer ScienceCombinatoricsPermutation010201 computation theory & mathematicsLehmer codeStatistics[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]FOS: Mathematics0202 electrical engineering electronic engineering information engineeringMathematics - CombinatoricsDiscrete Mathematics and CombinatoricsCombinatorics (math.CO)Bijection injection and surjectionComputingMilieux_MISCELLANEOUSMathematics
researchProduct

A new Euler–Mahonian constructive bijection

2011

AbstractUsing generating functions, MacMahon proved in 1916 the remarkable fact that the major index has the same distribution as the inversion number for multiset permutations, and in 1968 Foata gave a constructive bijection proving MacMahon’s result. Since then, many refinements have been derived, consisting of adding new constraints or new statistics.Here we give a new simple constructive bijection between the set of permutations with a given number of inversions and those with a given major index. We introduce a new statistic, mix, related to the Lehmer code, and using our new bijection we show that the bistatistic (mix,INV) is Euler–Mahonian. Finally, we introduce the McMahon code for …

Discrete mathematicsMultisetMathematics::CombinatoricsApplied MathematicsMajor indexMajor indexConstructiveCombinatoricssymbols.namesakeConstructive bijectionLehmer codeBijectionEuler's formulasymbolsInversion numberDiscrete Mathematics and CombinatoricsPermutation (bi)statisticStatisticMathematicsDiscrete Applied Mathematics
researchProduct

Transmission of Genetic Properties in Permutation Problems: Study of Lehmer Code and Inversion Table Encoding

2021

Solution encoding describes the way decision variables are represented. In the case of permutation problems, the classical encoding should ensure that there are no duplicates. During crossover operations, repairs may be carried out to correct or avoid repetitions. The use of indirect encoding aims to define bijections between the classical permutation and a different representation of the decision variables. These encodings are not sensitive to duplicates. However, they lead to a loss of genetic properties during crossbreeding. This paper proposes a study of the impact of this loss both in the space of decision variables and in that of fitness values. We consider two indirect encoding: the …

PermutationTransmission (telecommunications)Computer scienceEncoding (memory)Lehmer codeGenetic algorithmCrossoverArithmeticRepresentation (mathematics)Bijection injection and surjection
researchProduct